class Solution:
    temp: str = ""
    dp = []
    def count(self, left: int, right: int) -> int:
        if left > right:
            return 0

        if left == right:
            return 1

        if Solution.dp[left][right] != -1:
            return Solution.dp[left][right]

        if Solution.temp[left] == Solution.temp[right]:
            Solution.dp[left + 1][right - 1] = self.count(left + 1, right - 1)
            Solution.dp[left][right] = Solution.dp[left + 1][right - 1] + 2
            return Solution.dp[left][right]
        else:
            Solution.dp[left + 1][right] = self.count(left + 1, right)
            Solution.dp[left][right - 1] = self.count(left, right - 1)
            return max(
                Solution.dp[left + 1][right],
                Solution.dp[left][right - 1]
            )

    def longestPalindromeSubseq(self, s: str) -> int:
        Solution.temp = s
        Solution.dp = [[-1 for __ in range(len(s))] for _ in range(len(s))]
        return self.count(0, len(s) - 1)
